class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        stack<int> st;
        if(height.size() == 0) return sum;
        st.push(0);
        for(int i = 0;i < height.size();i++){
            while(!st.empty() && height[i] > height[st.top()]){
                int height1 = height[st.top()];
                st.pop();
                if(!st.empty()){
                    int height2 = min(height[st.top()],height[i]);
                    sum += (i - st.top() - 1) * (height2 - height1);
                }
            }
            st.push(i);
        }
        return sum;
    }
};
